package leetcode_day._2021._202104._2131;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/30 9:03
 * 只出现一次的数字
 * 只有一个数字只出现了一次，其余的都两次及以上
 * 可以使用异或运算
 * 0 ^ x = x
 * x ^ x = 0
 * 第一种：使用散列表记录数字出现的次数
 * 第二种：先排序，然后比较当前元素的前后
 */
public class _30_137 {

    public int singleNumber_one(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums)
            map.put(num, map.getOrDefault(num, 0) + 1);
        for (Map.Entry<Integer, Integer> entry : map.entrySet())
            if (1 == entry.getValue()) return entry.getKey();
        return nums[0];
    }

    public int singleNumber_two(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if ((i != nums.length - 1 && nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
            || (i == nums.length - 1 && nums[i] != nums[i - 1])) return nums[i];
        }
        return nums[0];
    }
}
